; Exercise 1.22
; Most Lisp implementations include a primitive called runtime that returns an
; integer that specifies the amount of time the system has been running
; (measured, for example, in microseconds). The following timed-prime-test
; procedure, when called with an integer n, prints n and checks to see if n
; is prime. If n is prime, the procedure prints three asterisks followed by
; the amount of time used in performing the test.
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
; Using this procedure, write a procedure search-for-primes that checks the
; primality of consecutive odd integers in a specified range. Use your procedure
; to find the three smallest primes larger than 1000; larger than 10,000; larger
; than 100,000; larger than 1,000,000. Note the time needed to test each prime.
; Since the testing algorithm has order of growth of [theta] ([sqrt] (n)), you
; should expect that testing for primes around 10,000 should take about [sqrt]
; (10) times as long as testing for primes around 1000. Do your timing data
; bear this out? How well do the data for 100,000 and 1,000,000 support the
; [sqrt] (n) prediction? Is your result compatible with the notion that
; programs on your machine run in time proportional to the number of steps
; required for the computation?
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (prime? n)
  (= n (smallest-divisor n)))

(define (find-primes-in-range a b)
  (cond ((> a b)
          (newline)
          (display "Fim"))
        ((even? a) (find-primes-in-range (+ a 1) b))
        (else 
          (timed-prime-test a)
          (find-primes-in-range (+ a 2) b))))
; 1009, 1013 e 1019
; 10007, 10009 e 10037
; 100003, 100019 e 100043
; 1000003, 1000033 e 1000037
; 10000000019 *** .3
; 10000000033 *** .29999999999999993
; 10000000061 *** .31000000000000005
; 100000000003 *** 1.0199999999999996
; 100000000019 *** .9800000000000004
; 100000000057 *** .9800000000000004
; 1000000000039 *** 3.1000000000000014 
; 1000000000061 *** 3.1099999999999994
; 1000000000063 *** 3.080000000000002
; O resultado segue a previsão para números maiores do que os sugeridos.
; A função tempo resulta em zero para os valores sugeridos.
